package _11_整理题目._1_链表指针._翻转链表;


import org.junit.Test;
import util.ListNode;

/**
 * 将一个链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。
 * 例如：
 * 给出的链表为 1 2 3 4 5 null, m=2,n=4,
 * 返回 1 4 3 2 5.
 * 注意：
 * 给出的 m,n 满足以下条件：
 * 1 < m < n < 链表长度
 * 
 * 参考上一题  《链表中的节点每k个一组翻转》  
 * 根据需要 至少需要 三个指针  可能删除第一个节点所以加个 fake node
 * 移动指针，让 pre 指向第 m-1 个节点，让 slow 指向第 m 个节点，fast 指向第 n+1 个节点
 * 调用翻转函数翻转，返回的 newHead 是第 n 个节点，尾结点是 slow 节点
 * 拼接返回的链表：pre.next = newHead; slow.next = fast;
 * 
 */
public class _01_链表内指定区间反转 {
    
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode fake = new ListNode(0);
        fake.next = head;
        
        ListNode fast = fake;
        ListNode pre = fake;
        while (m-- > 1) {
            pre = pre.next;
        }
        ListNode slow = pre.next;
        while (n-- > -1) {
            fast = fast.next;
        }
        ListNode newHead = rever(slow, fast);
        pre.next = newHead;
        slow.next = fast;
        return fake.next;
    }
    
    private ListNode rever(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
    
    @Test
    public void main() {
        Integer[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        ListNode head = ListNode.getListFromArray(array);
        ListNode.printList(head);
        ListNode result = reverseBetween(head, 1, 5);
        ListNode.printList(result);
    }
}
